package com.example.practice.class04;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Date 2022/9/12
 * @Author Jonathan
 * @Description <p/>数组为{3, 2, 2, 3, 1}，查询为(0, 3, 2)，意思是在数组里下标0~3这个范围上，有几个？
 * 答案返回2假设给你一个数组arr，对这个数组的查询非常频繁，且都给了查询组，请返回所有查询的结果
 * <>
 * 统计每一个出现的下标位置
 * </>
 */
public class Code01_FrequentSelectArray {
    static int[] arr = new int[]{3, 2, 2, 3, 1, 4, 2, 3, 5, 6, 3};
    static Map<Integer, List<Integer>> map = new HashMap<>();

    static {
        // 初始化这个map
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                map.get(arr[i]).add(i);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(arr[i], list);
            }
        }
    }

    public static void main(String[] args) {
        // 频繁的查询的效率就是 O(logN)
        final int num = getNum(0, arr.length - 1, 2);
        System.out.println(num);
    }

    public static int getNum(int indexFrom, int indexTo, int target) {
        // 将每个元素出现的下标统计起来
        if (!map.containsKey(target)) {
            return 0;
        }
        final List<Integer> list = map.get(target);
        final int upperIndex = getUpperIndex(list, indexFrom);
        final int lowerIndex = getLowerIndex(list, indexTo);
        return lowerIndex - upperIndex + 1;
    }

    private static int getUpperIndex(List<Integer> list, int target) {
        int left = 0;
        int right = list.size() - 1;
        int index = -1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (list.get(mid) >= target) {
                index = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return index;
    }

    private static int getLowerIndex(List<Integer> arr, int num) {
        // -1 表示不存在
        if (arr == null || arr.size() < 1) {
            return -1;
        }
        int L = 0;
        int R = arr.size() - 1;
        int index = -1;
        while (L <= R) {
            int M = L + ((R - L) >> 1);
            // 要找第一个比num小的索引下标
            if (arr.get(M) > num) {
                R = M - 1;
            } else {
                L = M + 1;
                index = M;
            }
        }
        return index;
    }


}
